{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize Result by Adding Parentheses to Expression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizeResult"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #向表达式添加括号后的最小结果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的字符串 <code>expression</code> ，格式为 <code>\"&lt;num1&gt;+&lt;num2&gt;\"</code> ，其中 <code>&lt;num1&gt;</code> 和 <code>&lt;num2&gt;</code> 表示正整数。</p>\n",
    "\n",
    "<p>请你向 <code>expression</code> 中添加一对括号，使得在添加之后， <code>expression</code> 仍然是一个有效的数学表达式，并且计算后可以得到 <strong>最小</strong> 可能值。左括号 <strong>必须</strong> 添加在 <code>'+'</code> 的左侧，而右括号必须添加在 <code>'+'</code> 的右侧。</p>\n",
    "\n",
    "<p>返回添加一对括号后形成的表达式&nbsp;<code>expression</code> ，且满足<em> </em><code>expression</code><em> </em>计算得到 <strong>最小</strong> 可能值<em>。</em>如果存在多个答案都能产生相同结果，返回任意一个答案。</p>\n",
    "\n",
    "<p>生成的输入满足：<code>expression</code> 的原始值和添加满足要求的任一对括号之后 <code>expression</code> 的值，都符合 32-bit 带符号整数范围。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>expression = \"247+38\"\n",
    "<strong>输出：</strong>\"2(47+38)\"\n",
    "<strong>解释：</strong>表达式计算得到 2 * (47 + 38) = 2 * 85 = 170 。\n",
    "注意 \"2(4)7+38\" 不是有效的结果，因为右括号必须添加在 <code>'+' 的右侧。</code>\n",
    "可以证明 170 是最小可能值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>expression = \"12+34\"\n",
    "<strong>输出：</strong>\"1(2+3)4\"\n",
    "<strong>解释：</strong>表达式计算得到 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>expression = \"999+999\"\n",
    "<strong>输出：</strong>\"(999+999)\"\n",
    "<strong>解释：</strong>表达式计算得到 999 + 999 = 1998 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= expression.length &lt;= 10</code></li>\n",
    "\t<li><code>expression</code> 仅由数字 <code>'1'</code> 到 <code>'9'</code> 和 <code>'+'</code> 组成</li>\n",
    "\t<li><code>expression</code> 由数字开始和结束</li>\n",
    "\t<li><code>expression</code> 恰好仅含有一个 <code>'+'</code>.</li>\n",
    "\t<li><code>expression</code> 的原始值和添加满足要求的任一对括号之后 <code>expression</code> 的值，都符合 32-bit 带符号整数范围</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-result-by-adding-parentheses-to-expression](https://leetcode.cn/problems/minimize-result-by-adding-parentheses-to-expression/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-result-by-adding-parentheses-to-expression](https://leetcode.cn/problems/minimize-result-by-adding-parentheses-to-expression/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"247+38\"', '\"12+34\"', '\"999+999\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        ans_exp, ans_val = '(' + expression + ')', eval(expression)\n",
    "        for i in range(len(left)):\n",
    "            left1, left2 = left[ : i ], left[ i : ]\n",
    "            for j in range(1, len(right) + 1):\n",
    "                right1, right2 = right[ : j ], right[ j : ]\n",
    "                tmp = int(left1 or 1) * (int(left2) + int(right1)) * int(right2 or 1)\n",
    "                if tmp < ans_val:\n",
    "                    ans_exp, ans_val = left1 + '(' + left2 + '+' + right1 + ')' + right2, tmp\n",
    "        return ans_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        def cal(expression: str) -> int:\n",
    "            l = expression.find('(')\n",
    "            idx = expression.find('+')\n",
    "            r = expression.find(')')\n",
    "            num1 = int(expression[ : l]) if expression[ : l] else 1\n",
    "            exp = expression[l+1 : r] \n",
    "            num2 = int(expression[r+1 :]) if expression[r+1 :] else 1\n",
    "            return num1 * eval(exp) * num2\n",
    "        idx = expression.find('+')\n",
    "        min_val = float('inf')\n",
    "        min_exp = \"\"\n",
    "        for i in range(idx):\n",
    "            for j in range(idx + 2, len(expression) + 1):\n",
    "                cur_exp = expression[:i] + '(' + expression[i : j] + ')' + expression[j :]\n",
    "                \n",
    "                cur_val = cal(cur_exp)\n",
    "                if cur_val < min_val:\n",
    "                    min_val = cur_val\n",
    "                    min_exp = cur_exp\n",
    "    \n",
    "        return min_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        # Split the expression into two operands\n",
    "        nums = expression.split('+')\n",
    "        x = nums[0].strip('\"')\n",
    "        y = nums[1].strip('\"')\n",
    "        \n",
    "        forms = {}\n",
    "        \n",
    "        # Iterate over the characters of the first operand\n",
    "        for i in range(len(x)):\n",
    "            x0 = list(x)\n",
    "            x0.insert(i, '(')\n",
    "            \n",
    "            # Iterate over the characters of the second operand\n",
    "            for j in range(len(y)):\n",
    "                y0 = list(y)\n",
    "                y0.insert(j+1, ')')\n",
    "                \n",
    "                # Combine the operands with parentheses and '+'\n",
    "                formula = ''.join(x0 + ['+'] + y0)\n",
    "                \n",
    "                # Calculate the total for different cases of parentheses\n",
    "                if formula[0] == '(' and formula[-1] != ')':\n",
    "                    total = eval(formula.replace(')', ')*'))\n",
    "                elif formula[0] != '(' and formula[-1] == ')':\n",
    "                    total = eval(formula.replace('(', '*('))\n",
    "                elif formula[0] != '(' and formula[-1] != ')':\n",
    "                    formula0 = formula.replace(')', ')*')\n",
    "                    total = eval(formula0.replace('(', '*('))\n",
    "                else:\n",
    "                    total = eval(formula)\n",
    "                \n",
    "                forms[total] = formula\n",
    "        \n",
    "        # Find the formula with the minimum total\n",
    "        min_total = min(forms.keys())\n",
    "        \n",
    "        # Return the formula corresponding to the minimum total\n",
    "        return forms[min_total]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        a, b = expression.split('+')\n",
    "        l1, l2 = len(a), len(b)\n",
    "        p1, p2 , min_ = l1-1, 1, float('inf')\n",
    "        while p1 >=0:\n",
    "            while p2 <= l2:\n",
    "                cur = (int(a[p1:])+int(b[:p2])) * (1 if p1 == 0 else int(a[:p1])) * (1 if p2 == l2 else int(b[p2:]))\n",
    "                #int('123') 可直接字符串转数字\n",
    "                #a[p1:] 从下标的 p1 开始到最后 \n",
    "                #a[p1, p1] 是空\n",
    "                #字符串可以用[:l]来 切片\n",
    "                if cur < min_: l, r, min_ = p1, p2, cur\n",
    "                p2 += 1\n",
    "                #print(min_, l, r)\n",
    "            p1, p2 = p1-1, 1\n",
    "        return expression[:l] + '(' + expression[l:l1 + r + 1] + ')' + expression[l1 + r + 1:]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        ans_exp, ans_val = '(' + expression + ')', eval(expression)\n",
    "        for i in range(len(left)):\n",
    "            left1, left2 = left[ : i ], left[ i : ]\n",
    "            for j in range(1, len(right) + 1):\n",
    "                right1, right2 = right[ : j ], right[ j : ]\n",
    "                tmp = int(left1 or 1) * (int(left2) + int(right1)) * int(right2 or 1)\n",
    "                if tmp < ans_val:\n",
    "                    ans_exp, ans_val = left1 + '(' + left2 + '+' + right1 + ')' + right2, tmp\n",
    "        return ans_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        ans = eval(expression)\n",
    "        res = \"(\"+expression[:]+')'\n",
    "        num1, num2 = expression.split(\"+\")\n",
    "        for l in range(len(num1)):\n",
    "            for r in range(len(expression)-len(num2), len(expression)):\n",
    "                lc = expression[:l] if expression[:l] else '1'\n",
    "                rc = expression[r+1:len(expression)] if expression[r+1:len(expression)] else \"1\"\n",
    "                val = eval(lc+\"*(\"+expression[l:r+1]+\")*\"+rc)\n",
    "                if val < ans:\n",
    "                    ans = val\n",
    "                    res = expression[:l]+\"(\"+expression[l:r+1]+\")\"+expression[r+1:len(expression)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        l, r = int(left), int(right)\n",
    "        # ans储存第一个括号左边有几个数，加号到第二个括号之间有几个数\n",
    "        ans = (0, len(right))\n",
    "        mn = l + r\n",
    "        \n",
    "        for i in range(len(left)):\n",
    "            l1 = int(left[:i] or 1)\n",
    "            l2 = int(left[i:] or 0)\n",
    "            # 加号不能在结尾，例如'(123+)234'\n",
    "            for j in range(1, len(right) + 1):\n",
    "                r1 = int(right[:j])\n",
    "                r2 = int(right[j:] or 1)\n",
    "                total = l1 * (l2 + r1) * r2\n",
    "                if total < mn:\n",
    "                    mn = total\n",
    "                    ans = (i, j)\n",
    "        \n",
    "        i, j = ans\n",
    "        return ''.join((left[:i], '(', left[i:], '+', right[:j], ')', right[j:]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        ans_exp, ans_val = '(' + expression + ')', eval(expression)\n",
    "        for i in range(len(left)):\n",
    "            left1, left2 = left[:i], left[i:]\n",
    "            for j in range(1, len(right) + 1):\n",
    "                right1, right2 = right[:j], right[j:]\n",
    "                tmp = int(left1 or 1) * (int(left2) + int(right1)) * int(right2 or 1)\n",
    "                if tmp < ans_val:\n",
    "                    ans_exp, ans_val = left1 + '(' + left2 + '+' + right1 + ')' + right2, tmp\n",
    "        return ans_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        def cal(expression: str) -> int:\n",
    "            l = expression.find('(')\n",
    "            idx = expression.find('+')\n",
    "            r = expression.find(')')\n",
    "            num1 = int(expression[ : l]) if expression[ : l] else 1\n",
    "            exp = expression[l+1 : r] \n",
    "            num2 = int(expression[r+1 :]) if expression[r+1 :] else 1\n",
    "            return num1 * eval(exp) * num2\n",
    "        idx = expression.find('+')\n",
    "        min_val = float('inf')\n",
    "        min_exp = \"\"\n",
    "        for i in range(idx):\n",
    "            for j in range(idx + 2, len(expression) + 1):\n",
    "                cur_exp = expression[:i] + '(' + expression[i : j] + ')' + expression[j :]\n",
    "                \n",
    "                cur_val = cal(cur_exp)\n",
    "                if cur_val < min_val:\n",
    "                    min_val = cur_val\n",
    "                    min_exp = cur_exp\n",
    "    \n",
    "        return min_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        # ans储存第一个括号左边有几个数，加号到第二个括号之间有几个数\n",
    "        ans = 0\n",
    "        mn = inf\n",
    "        \n",
    "        for i in range(len(left)):\n",
    "            l1 = int(left[:i] or 1)\n",
    "            l2 = int(left[i:] or 0)\n",
    "            # 加号不能在结尾，例如'(123+)234'\n",
    "            for j in range(1, len(right) + 1):\n",
    "                r1 = int(right[:j])\n",
    "                r2 = int(right[j:] or 1)\n",
    "                total = l1 * (l2 + r1) * r2\n",
    "                if total < mn:\n",
    "                    mn = total\n",
    "                    ans = (i, j)\n",
    "        \n",
    "        i, j = ans\n",
    "        return ''.join((left[:i], '(', expression[i:len(left)+1+j], ')', right[j:]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        plus_pos = 0\n",
    "        while expression[plus_pos] != \"+\":\n",
    "            plus_pos += 1\n",
    "        n = len(expression)\n",
    "        min_result = (2**31) - 1\n",
    "        min_exp = \"\"\n",
    "        for right_pos in range(plus_pos + 1, n):\n",
    "            expression1 = (\n",
    "                expression[: right_pos + 1] + \")\" + expression[right_pos + 1 :]\n",
    "            )\n",
    "            for left_pos in range(plus_pos):\n",
    "                expression2 = expression1[:left_pos] + \"(\" + expression1[left_pos:]\n",
    "                temp_result = self.calc_result(expression2)\n",
    "                if temp_result < min_result:\n",
    "                    min_result = temp_result\n",
    "                    min_exp = expression2\n",
    "        return min_exp\n",
    "\n",
    "    def calc_result(self, expression: str) -> str:\n",
    "        left_pos, right_pos = 0, 0\n",
    "        while expression[left_pos] != \"(\":\n",
    "            left_pos += 1\n",
    "        while expression[right_pos] != \")\":\n",
    "            right_pos += 1\n",
    "        left_mult = 1 if left_pos == 0 else int(expression[:left_pos])\n",
    "        right_mult = (\n",
    "            1 if right_pos == len(expression) - 1 else int(expression[right_pos + 1 :])\n",
    "        )\n",
    "        mid_nums = expression[left_pos + 1 : right_pos].split(\"+\")\n",
    "        return left_mult * (int(mid_nums[0]) + int(mid_nums[1])) * right_mult"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        # Split the expression into two operands\n",
    "        nums = expression.split('+')\n",
    "        x = nums[0].strip('\"')\n",
    "        y = nums[1].strip('\"')\n",
    "        \n",
    "        forms = {}\n",
    "        \n",
    "        # Iterate over the characters of the first operand\n",
    "        for i in range(len(x)):\n",
    "            x0 = list(x)\n",
    "            x0.insert(i, '(')\n",
    "            \n",
    "            # Iterate over the characters of the second operand\n",
    "            for j in range(len(y)):\n",
    "                y0 = list(y)\n",
    "                y0.insert(j+1, ')')\n",
    "                \n",
    "                # Combine the operands with parentheses and '+'\n",
    "                formula = ''.join(x0 + ['+'] + y0)\n",
    "                \n",
    "                # Calculate the total for different cases of parentheses\n",
    "                if formula[0] == '(' and formula[-1] != ')':\n",
    "                    total = eval(formula.replace(')', ')*'))\n",
    "                elif formula[0] != '(' and formula[-1] == ')':\n",
    "                    total = eval(formula.replace('(', '*('))\n",
    "                elif formula[0] != '(' and formula[-1] != ')':\n",
    "                    formula0 = formula.replace(')', ')*')\n",
    "                    total = eval(formula0.replace('(', '*('))\n",
    "                else:\n",
    "                    total = eval(formula)\n",
    "                \n",
    "                forms[total] = formula\n",
    "        \n",
    "        # Find the formula with the minimum total\n",
    "        min_total = min(forms.keys())\n",
    "        \n",
    "        # Return the formula corresponding to the minimum total\n",
    "        return forms[min_total]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        def cal(expression: str) -> int:\n",
    "            l = expression.find('(')\n",
    "            idx = expression.find('+')\n",
    "            r = expression.find(')')\n",
    "            num1 = int(expression[ : l]) if expression[ : l] else 1\n",
    "            exp = expression[l+1 : r] \n",
    "            num2 = int(expression[r+1 :]) if expression[r+1 :] else 1\n",
    "            return num1 * eval(exp) * num2\n",
    "        idx = expression.find('+')\n",
    "        min_val = float('inf')\n",
    "        min_exp = \"\"\n",
    "        for i in range(idx):\n",
    "            for j in range(idx + 2, len(expression) + 1):\n",
    "                cur_exp = expression[:i] + '(' + expression[i : j] + ')' + expression[j :]\n",
    "                \n",
    "                cur_val = cal(cur_exp)\n",
    "                if cur_val < min_val:\n",
    "                    min_val = cur_val\n",
    "                    min_exp = cur_exp\n",
    "    \n",
    "        return min_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        a,b=map(str,expression.split('+'))\n",
    "        t=int(a)+int(b)\n",
    "        I=0\n",
    "        J=len(b)\n",
    "        for i in range(1,len(a)):\n",
    "            r=int(a[0:i])*(int(a[i:])+int(b))\n",
    "            t=min(t,r)\n",
    "            if r==t:\n",
    "                I=i\n",
    "                J=len(b)\n",
    "        for i in range(1,len(b)):\n",
    "            r=int(b[i:])*(int(a)+int(b[0:i]))\n",
    "            t=min(t,r)\n",
    "            if r==t:\n",
    "                I=0\n",
    "                J=i\n",
    "        for i in range(1,len(a)):\n",
    "            for j in range(1,len(b)):\n",
    "                r=int(a[0:i])*(int(a[i:])+int(b[0:j]))*int(b[j:])\n",
    "                t=min(t,r)\n",
    "                if r==t:\n",
    "                    I=i\n",
    "                    J=j\n",
    "        return a[:I]+'('+a[I:]+'+'+b[:J]+')'+b[J:]\n",
    "        \n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        idx = expression.index('+')\n",
    "        ans = '(' + expression + ')'\n",
    "        best = eval(ans)\n",
    "        for i in range(0, idx):\n",
    "            for j in range(idx + 1, len(expression)):\n",
    "                s = expression[:i] + '*(' + expression[i:j + 1] + ')*' + expression[j + 1:]\n",
    "                if s.startswith('*'):\n",
    "                    s = s[1:]\n",
    "                if s.endswith('*'):\n",
    "                    s = s[:-1]\n",
    "                val = eval(s)\n",
    "                if val < best:\n",
    "                    ans = s.replace('*', '')\n",
    "                    best = val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        def cal(expression: str) -> int:\n",
    "            l = expression.find('(')\n",
    "            idx = expression.find('+')\n",
    "            r = expression.find(')')\n",
    "            num1 = int(expression[ : l]) if expression[ : l] else 1\n",
    "            exp = expression[l+1 : r] \n",
    "            num2 = int(expression[r+1 :]) if expression[r+1 :] else 1\n",
    "            return num1 * eval(exp) * num2\n",
    "        idx = expression.find('+')\n",
    "        min_val = float('inf')\n",
    "        min_exp = \"\"\n",
    "        for i in range(idx):\n",
    "            for j in range(idx + 2, len(expression) + 1):\n",
    "                cur_exp = expression[:i] + '(' + expression[i : j] + ')' + expression[j :]\n",
    "                \n",
    "                cur_val = cal(cur_exp)\n",
    "                if cur_val < min_val:\n",
    "                    min_val = cur_val\n",
    "                    min_exp = cur_exp\n",
    "    \n",
    "        return min_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        res, m = '', 10 ** 9\n",
    "        s1, s2 = expression.split('+')\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        for left in range(n1):\n",
    "            x1 = 1 if left == 0 else int(s1[:left])\n",
    "            x2 = int(s1[left:])\n",
    "            for right in range(n2):\n",
    "                x3 = int(s2[:n2-right])\n",
    "                x4 = 1 if right == 0 else int(s2[n2-right:])\n",
    "                v = x1 * (x2 + x3) * x4\n",
    "                if v < m:\n",
    "                    m = v\n",
    "                    res = s1[:left] + '(' + s1[left:] + '+' + s2[:n2-right] + ')' + s2[n2-right:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        n = len(expression)\n",
    "        mid = expression.index(\"+\")\n",
    "        best, ans = float(\"inf\"), \"\"\n",
    "        for i in range(mid):\n",
    "            for j in range(mid + 1, n):\n",
    "                result = int(expression[:i] or 1) * (int(expression[i:mid]) + int(expression[mid+1:j+1])) * int(expression[j+1:] or 1)\n",
    "                if result < best:\n",
    "                    best = result\n",
    "                    ans = expression[:i] + \"(\" + expression[i:j+1] + \")\" + expression[j+1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        ans_exp, ans_val = '(' + expression + ')', eval(expression)\n",
    "        for i in range(len(left)):\n",
    "            left1, left2 = left[ : i ], left[ i : ]\n",
    "            for j in range(1, len(right) + 1):\n",
    "                right1, right2 = right[ : j ], right[ j : ]\n",
    "                tmp = int(left1 or 1) * (int(left2) + int(right1)) * int(right2 or 1)\n",
    "                if tmp < ans_val:\n",
    "                    ans_exp, ans_val = left1 + '(' + left2 + '+' + right1 + ')' + right2, tmp\n",
    "        return ans_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "\n",
    "        res_exp, res_val = '(' + expression + ')', eval(expression)\n",
    "        left, right = expression.split('+')\n",
    "        # ans_exp, ans_val = '(' + expression + ')', eval(expression\n",
    "        \n",
    "        for i in range(len(left)):\n",
    "            l1, l2 = left[:i], left[i:]\n",
    "            for j in range(1, len(right)+1): # the first position is not considered\n",
    "                r1, r2 = right[:j], right[j:]\n",
    "                \n",
    "                check = int(l1 or 1) * (int(l2)+int(r1)) * int(r2 or 1)\n",
    "\n",
    "                if check < res_val:\n",
    "                    res_val = check\n",
    "                    res_exp = f'{l1}({l2}+{r1}){r2}'\n",
    "        return res_exp\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(len(left)):\n",
    "            left1, left2 = left[ : i ], left[ i : ]\n",
    "            for j in range(1, len(right) + 1):\n",
    "                right1, right2 = right[ : j ], right[ j : ]\n",
    "                tmp = int(left1 or 1) * (int(left2) + int(right1)) * int(right2 or 1)\n",
    "                if tmp < ans_val:\n",
    "                    ans_exp, ans_val = left1 + '(' + left2 + '+' + right1 + ')' + right2, tmp\n",
    "        return ans_exp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        l, r = expression.split(\"+\")\n",
    "        nl = len(l)\n",
    "        nr = len(r)\n",
    "        cnt = inf\n",
    "        ans = \"\"\n",
    "        for i in range(nl):\n",
    "            tmpi1 = 1 if i == 0 else int(l[:i])\n",
    "            tmpi2 = int(l[i:])\n",
    "            for j in range(1, nr + 1):\n",
    "                tmpj1 = int(r[:j])\n",
    "                tmpj2 = int(r[j:]) if j < nr else 1\n",
    "                if tmpi1 * (tmpi2 + tmpj1) * tmpj2 < cnt:\n",
    "                    cnt = tmpi1 * (tmpi2 + tmpj1) * tmpj2\n",
    "                    ans = l[:i] + \"(\" + l[i:] + \"+\" + r[:j] + \")\" + r[j:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        a,b=expression.split(\"+\")\n",
    "        \n",
    "        \n",
    "        m=len(a)\n",
    "        n=len(b)\n",
    "        ans=int(a)+int(b)\n",
    "        ct0='('+expression+')'\n",
    "        for i in range(m-1):\n",
    "            for j in range(n-1):\n",
    "                p=int(a[:(i+1)])\n",
    "                q=int(a[(i+1):])\n",
    "                s=int(b[:(j+1)])\n",
    "                t=int(b[(j+1):])\n",
    "                if p*(q+s)*t<ans:\n",
    "                    ct0=a[:(i+1)] + \"(\" + a[(i+1):] + \"+\" + b[:(j+1)] + \")\" + b[(j+1):]\n",
    "                    ans=p*(q+s)*t\n",
    "        ct1=ct2=\"\"\n",
    "        for u in range(m-1):\n",
    "            l=int(a[:u+1])*(int(a[u+1:])+int(b))\n",
    "            if l<ans:\n",
    "                ct0=a[:(u+1)] + \"(\" + a[(u+1):] + \"+\" + b + \")\"\n",
    "                ans=l\n",
    "        for v in range(n-1):\n",
    "            r=(int(b[(v+1):]))*(int(b[:(v+1)])+int(a))\n",
    "            if r<ans:\n",
    "                ct0=\"(\" + a + \"+\" + b[:(v+1)] + \")\" + b[(v+1):]\n",
    "                ans=r\n",
    "        return ct0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        expression=expression.split(\"+\")\n",
    "        a=expression[0]\n",
    "        b=expression[1]\n",
    "        alen=len(str(a))\n",
    "        blen=len(str(b))\n",
    "        ans=int(a)+int(b)\n",
    "\n",
    "        lst=[]\n",
    "        for i in range(alen):\n",
    "            for j in range(blen):\n",
    "                if i==0:\n",
    "                    num1=0\n",
    "                    num2=int(a)\n",
    "                else:\n",
    "                    num1=int(a[:i])\n",
    "                    num2=int(a[i:])\n",
    "                if j==blen-1:\n",
    "                    num3=int(b)\n",
    "                    num4=0\n",
    "                else:\n",
    "                    num3=int(b[:j+1])\n",
    "                    num4=int(b[j+1:])\n",
    "                ans1=(num2+num3)*max(1,num1)*max(1,num4)\n",
    "\n",
    "                if ans1<=ans:\n",
    "                    ans=ans1\n",
    "                    lst.clear()\n",
    "                    lst.append(num1)\n",
    "                    lst.append(num2)\n",
    "                    lst.append(num3)\n",
    "                    lst.append(num4)\n",
    "\n",
    "        if lst[0]==0 and lst[3]==0:\n",
    "            d=\"(\"+a+\"+\"+b+\")\"\n",
    "        elif lst[0]==0 and lst[3]!=0:\n",
    "            d=\"(\"+a+\"+\"+str(lst[2])+\")\"+str(lst[3])\n",
    "        elif lst[0]!=0 and lst[3]==0:\n",
    "            d=str(lst[0])+\"(\"+str(lst[1])+\"+\"+b+\")\"\n",
    "        else:\n",
    "            d=str(lst[0])+\"(\"+str(lst[1])+\"+\"+str(lst[2])+\")\"+str(lst[3])\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        expression=expression.split(\"+\")\n",
    "        a=expression[0]\n",
    "        b=expression[1]\n",
    "        alen=len(str(a))\n",
    "        blen=len(str(b))\n",
    "        ans=int(a)+int(b)\n",
    "\n",
    "        lst=[]\n",
    "        for i in range(alen):\n",
    "            for j in range(blen):\n",
    "                if i==0:\n",
    "                    num1=0\n",
    "                    num2=int(a)\n",
    "                else:\n",
    "                    num1=int(a[:i])\n",
    "                    num2=int(a[i:])\n",
    "                if j==blen-1:\n",
    "                    num3=int(b)\n",
    "                    num4=0\n",
    "                else:\n",
    "                    num3=int(b[:j+1])\n",
    "                    num4=int(b[j+1:])\n",
    "                ans1=(num2+num3)*max(1,num1)*max(1,num4)\n",
    "\n",
    "                if ans1<=ans:\n",
    "                    ans=ans1\n",
    "                    lst.clear()\n",
    "                    lst.append(num1)\n",
    "                    lst.append(num2)\n",
    "                    lst.append(num3)\n",
    "                    lst.append(num4)\n",
    "\n",
    "        if lst[0]==0 and lst[3]==0:\n",
    "            d=\"(\"+a+\"+\"+b+\")\"\n",
    "        elif lst[0]==0 and lst[3]!=0:\n",
    "            d=\"(\"+a+\"+\"+str(lst[2])+\")\"+str(lst[3])\n",
    "        elif lst[0]!=0 and lst[3]==0:\n",
    "            d=str(lst[0])+\"(\"+str(lst[1])+\"+\"+b+\")\"\n",
    "        else:\n",
    "            d=str(lst[0])+\"(\"+str(lst[1])+\"+\"+str(lst[2])+\")\"+str(lst[3])\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        n=len(expression)\n",
    "        a=expression.index('+')\n",
    "        ans=[]\n",
    "        dic={}\n",
    "        for i in range(a):\n",
    "            for j in range(a+1,n+1):\n",
    "                result = int(expression[:i] or '1')*(int(expression[i:a])+int(expression[a+1:j] or '1'))*int(expression[j:] or '1')\n",
    "                ans.append(result)\n",
    "                dic[result]=expression[:i] +\"(\"+expression[i:a]+\"+\"+expression[a+1:j]+')'+expression[j:]\n",
    "        b=min(ans)\n",
    "        return dic[b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, s: str) -> str:\n",
    "        ans = inf\n",
    "        temp = None\n",
    "        st = []\n",
    "        i_add = s.find(\"+\")\n",
    "        for l in range(0, i_add):\n",
    "            a = int(s[0: l]) if l > 0 else 1\n",
    "            for r in range(i_add + 1, len(s)):\n",
    "                b = int(s[l: i_add]) + int(s[i_add + 1: r + 1])\n",
    "                c = int(s[r + 1: len(s)]) if r != len(s) - 1 else 1 \n",
    "                if a * b * c < ans:\n",
    "                    ans = a * b * c\n",
    "                    temp = (l, r)\n",
    "        l, r = temp\n",
    "        return s[:temp[0]] + \"(\" + s[l:r + 1] + \")\" + s[r + 1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        from itertools import product\n",
    "        left,right = expression.split('+')\n",
    "        nl,nr = len(left),len(right)\n",
    "        d = {}\n",
    "        for l,r in product(range(1,nl),range(1,nr)):\n",
    "            pleft,pright = list(left),list(right)\n",
    "            pleft.insert(l, '*(')\n",
    "            pright.insert(r,')*')\n",
    "            expr = ''.join(pleft) + '+' + ''.join(pright)\n",
    "            d[eval(expr)] = expr.replace('*','')\n",
    "        for r in range(1,nr):\n",
    "            pleft, pright = list(left), list(right)\n",
    "            pleft = ['('] + pleft\n",
    "            pright.insert(r, ')*')\n",
    "            expr = ''.join(pleft) + '+' + ''.join(pright)\n",
    "            d[eval(expr)] = expr.replace('*','')\n",
    "        for l in range(1,nl):\n",
    "            pleft, pright = list(left), list(right)\n",
    "            pright = pright + [')']\n",
    "            pleft.insert(l, '*(')\n",
    "            expr = ''.join(pleft) + '+' + ''.join(pright)\n",
    "            d[eval(expr)] = expr.replace('*','')\n",
    "        d[eval(expression)] = f'({expression})'\n",
    "        return (d[min(d.keys())])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        l, r = expression.split('+')\n",
    "        ln_l, ln_r = len(l), len(r)\n",
    "        d = Counter()\n",
    "        ans = ''\n",
    "        val = inf\n",
    "        for i in range(ln_l):\n",
    "            for j in range(ln_r):\n",
    "                a, b = l[:i], l[i:]\n",
    "                c, d = r[:j + 1], r[j + 1:]\n",
    "                tmp = (int(a) if a else 1) * (int(b) + int(c)) * (int(d) if d else 1)\n",
    "                if tmp < val:\n",
    "                    ans = a + '(' + b + '+' + c + ')' + d \n",
    "                    val = tmp \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        nums=expression.split('+')\n",
    "        l1=len(nums[0])\n",
    "        l2=len(nums[1])\n",
    "        a,b,s=0,l2,int(nums[0])+int(nums[1])\n",
    "        for i in range(1,l1):\n",
    "            for j in range(1,l2):\n",
    "                t=int(nums[0][0:i])*(int(nums[0][i:l1])+int(nums[1][0:j]))*int(nums[1][j:l2])\n",
    "                if t<s:\n",
    "                    a=i\n",
    "                    b=j\n",
    "                    s=t\n",
    "        for i in range(1,l1):\n",
    "            t=int(nums[0][0:i])*(int(nums[0][i:l1])+int(nums[1]))\n",
    "            if t<s:\n",
    "                a=i\n",
    "                b=l2\n",
    "                s=t\n",
    "        for j in range(1,l2):\n",
    "            t=(int(nums[0])+int(nums[1][0:j]))*int(nums[1][j:l2])\n",
    "            if t<s:\n",
    "                a=0\n",
    "                b=j\n",
    "                s=t\n",
    "        ans=nums[0][0:a]+'('+nums[0][a:l1]+'+'+nums[1][0:b]+')'+nums[1][b:l2]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        idx = expression.index('+')\n",
    "        ans = '(' + expression + ')'\n",
    "        best = eval(ans)\n",
    "        for i in range(0, idx):\n",
    "            for j in range(idx + 1, len(expression)):\n",
    "                s = expression[:i] + '*(' + expression[i:j + 1] + ')*' + expression[j + 1:]\n",
    "                if s.startswith('*'):\n",
    "                    s = s[1:]\n",
    "                if s.endswith('*'):\n",
    "                    s = s[:-1]\n",
    "                val = eval(s)\n",
    "                if val < best:\n",
    "                    ans = s.replace('*', '')\n",
    "                    best = val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        sp = expression.split('+')\n",
    "        lp,rp = sp[0],sp[1]\n",
    "        best =inf\n",
    "        ans =\"\" \n",
    "        for i in range(len(lp)):\n",
    "            for j in range(1,len(rp)+1):\n",
    "                res = int(lp[:i] or 1) * (int(lp[i:])+ int(rp[:j]))* int(rp[j:] or 1)\n",
    "                if res < best:\n",
    "                    best =res\n",
    "                    ans = lp[:i]+'('+lp[i:]+\"+\"+rp[:j]+\")\"+rp[j:]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def func(self, i, j, expression, lis, x, y):\n",
    "        n1, n2, n3, n4 = 0, 0, 0, 0\n",
    "        #lis = expression.split('+')\n",
    "        #x = len(lis[0])\n",
    "        #y = len(lis[1])\n",
    "        if i == 0:\n",
    "            n1 = 1\n",
    "        else:\n",
    "            for c in range(0, i):\n",
    "                n1 = n1 * 10 + ord(lis[0][c])-ord('0')\n",
    "        for c in range(i, x):\n",
    "                n2 = n2 * 10 + ord(lis[0][c])-ord('0')\n",
    "        for c in range(0, j+1):\n",
    "                n3 = n3 * 10 + ord(lis[1][c])-ord('0')\n",
    "        for c in range(j+1, y):\n",
    "                n4 = n4 * 10 + ord(lis[1][c])-ord('0')\n",
    "        if j+1 == y: n4 = 1\n",
    "        #print('ret ,n1, n2, n3, n4', ret, n1, n2, n3, n4)\n",
    "        return (n2 + n3) * n1 * n4\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        lis = expression.split('+')\n",
    "        x = len(lis[0])\n",
    "        y = len(lis[1])\n",
    "        res_x = 0\n",
    "        res_y = 0\n",
    "        res = -1\n",
    "        for i in range(x):\n",
    "            for j in range(y):\n",
    "                value = self.func(i, j, expression, lis, x, y) \n",
    "                if res > value or res == -1:\n",
    "                    res = value\n",
    "                    res_x = i\n",
    "                    res_y = j\n",
    "        #print('x, y, res' , res_x, res_y, res)\n",
    "        s_list = list(lis[0])\n",
    "        #i = s_list.index(c)\n",
    "        s_list.insert(res_x,'(')\n",
    "        s = ''.join(s_list)\n",
    "        s_list = list(lis[1])\n",
    "        #i = s_list.index(c)\n",
    "        s_list.insert(res_y+1,')')\n",
    "        t = ''.join(s_list)\n",
    "\n",
    "        return s + '+' + t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        expression=expression.split(\"+\")\n",
    "        a=expression[0]\n",
    "        b=expression[1]\n",
    "        alen=len(str(a))\n",
    "        blen=len(str(b))\n",
    "        ans=int(a)+int(b)\n",
    "\n",
    "        lst=[]\n",
    "        for i in range(alen):\n",
    "            for j in range(blen):\n",
    "                if i==0:\n",
    "                    num1=0\n",
    "                    num2=int(a)\n",
    "                else:\n",
    "                    num1=int(a[:i])\n",
    "                    num2=int(a[i:])\n",
    "                if j==blen-1:\n",
    "                    num3=int(b)\n",
    "                    num4=0\n",
    "                else:\n",
    "                    num3=int(b[:j+1])\n",
    "                    num4=int(b[j+1:])\n",
    "                ans1=(num2+num3)*max(1,num1)*max(1,num4)\n",
    "\n",
    "                if ans1<=ans:\n",
    "                    ans=ans1\n",
    "                    lst.clear()\n",
    "                    lst.append(num1)\n",
    "                    lst.append(num2)\n",
    "                    lst.append(num3)\n",
    "                    lst.append(num4)\n",
    "\n",
    "        if lst[0]==0 and lst[3]==0:\n",
    "            d=\"(\"+a+\"+\"+b+\")\"\n",
    "        elif lst[0]==0 and lst[3]!=0:\n",
    "            d=\"(\"+a+\"+\"+str(lst[2])+\")\"+str(lst[3])\n",
    "        elif lst[0]!=0 and lst[3]==0:\n",
    "            d=str(lst[0])+\"(\"+str(lst[1])+\"+\"+b+\")\"\n",
    "        else:\n",
    "            d=str(lst[0])+\"(\"+str(lst[1])+\"+\"+str(lst[2])+\")\"+str(lst[3])\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "       expression=expression.split('+')\n",
    "       m=expression[0]\n",
    "       n=expression[-1]\n",
    "       location=[0,len(n)]\n",
    "       sums=int(m)+int(n)\n",
    "       for i in range(len(m)-1,-1,-1):\n",
    "          x=int(m[i:]) if m[i:] else 0\n",
    "          a=m[0:i]\n",
    "          for j in range(1,len(n)+1):\n",
    "            y=int(n[0:j]) if n[0:j] else 0\n",
    "            b=n[j:]\n",
    "            if a:\n",
    "              temp=int(a)*(x+y)*int(b) if b else int(a)*(x+y)\n",
    "            else:\n",
    "              temp=(x+y)*int(b) if b else x+y\n",
    "            if temp<sums:\n",
    "                location=[i,j]\n",
    "                sums=temp\n",
    "       return (m[0:location[0]]+'('+m[location[0]:]+'+'+n[0:location[1]]+')'+n[location[1]:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "\n",
    "        jp=0\n",
    "        for i in range(len(expression)):\n",
    "            if expression[i]=='+':\n",
    "                jp=i\n",
    "                break\n",
    "        minv=-1\n",
    "        for i in range(0-1,jp-2+1):\n",
    "            for j in range(jp+1,len(expression)):\n",
    "\n",
    "                a=1 if i<0 else  int(expression[0:i+1])\n",
    "                #b=0 if i+1<=jp  else int(expression[i+1:jp])\n",
    "                b=int(expression[i+1:jp])\n",
    "                #c=0 if jp+1<j+1  else int(expression[jp+1:j+1])\n",
    "                c=int(expression[jp+1:j+1])\n",
    "                d=1 if j+1>=len(expression) else  int(expression[j+1:])\n",
    "\n",
    "                num= a*(b+c)*d\n",
    "                print(f'{a}*({b}+{c})*{d} = {num}')\n",
    "                if minv==-1:\n",
    "                    minv=num\n",
    "                    minstr=expression[0:i+1]+'('+expression[i+1:jp]+'+'+expression[jp+1:j+1]+')'+expression[j+1:]\n",
    "                elif num<minv:\n",
    "                    minv=min(num,minv)\n",
    "                    minstr=expression[0:i+1]+'('+expression[i+1:jp]+'+'+expression[jp+1:j+1]+')'+expression[j+1:]\n",
    "        return minstr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        ans_exp, ans_val = '(' + expression + ')', eval(expression)\n",
    "        for i in range(len(left)):\n",
    "            left1, left2 = left[ : i ], left[ i : ]\n",
    "            for j in range(1, len(right) + 1):\n",
    "                right1, right2 = right[ : j ], right[ j : ]\n",
    "                tmp = int(left1 or 1) * (int(left2) + int(right1)) * int(right2 or 1)\n",
    "                if tmp < ans_val:\n",
    "                    ans_exp, ans_val = left1 + '(' + left2 + '+' + right1 + ')' + right2, tmp\n",
    "        return ans_exp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        \n",
    "        ans = \"\"\n",
    "        res= inf\n",
    "        lst = list(expression)\n",
    "        i = lst.index(\"+\")\n",
    "        n = len(expression)\n",
    "        for x in range(i):\n",
    "            for y in range(i+1, n):\n",
    "                cur = lst[:]\n",
    "                if x:\n",
    "                    cur[x] = \"*(\" + cur[x]\n",
    "                else:\n",
    "                    cur[x] = \"(\" + cur[x]\n",
    "                if y < n-1:\n",
    "                    cur[y] = cur[y] + \")*\"\n",
    "                else:\n",
    "                    cur[y] = cur[y] + \")\"\n",
    "                st = \"\".join(cur)\n",
    "                val = eval(st)\n",
    "                if val < res:\n",
    "                    res = val\n",
    "                    ans = st.replace(\"*\", \"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        n = len(expression)\n",
    "        k = expression.find('+')\n",
    "        mn = eval(expression)\n",
    "        ans = expression\n",
    "        for i in range(k):\n",
    "            a = int(expression[:i]) if i > 0 else 1\n",
    "            for j in range(k + 1, n):\n",
    "                b = eval(expression[i:j+1])\n",
    "                c = int(expression[j+1:]) if j < n - 1 else 1\n",
    "                if a * b * c <= mn:\n",
    "                    mn = a * b * c\n",
    "                    ans = expression[:i] + '(' + expression[i:j+1] + ')' + expression[j+1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        ans_exp, ans_val = '(' + expression + ')', eval(expression)\n",
    "        for i in range(len(left)):\n",
    "            left1, left2 = left[ : i ], left[ i : ]\n",
    "            for j in range(1, len(right) + 1):\n",
    "                right1, right2 = right[ : j ], right[ j : ]\n",
    "                tmp = int(left1 or 1) * (int(left2) + int(right1)) * int(right2 or 1)\n",
    "                if tmp < ans_val:\n",
    "                    ans_exp, ans_val = left1 + '(' + left2 + '+' + right1 + ')' + right2, tmp\n",
    "        return ans_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        res = \"\"\n",
    "        plus_pos = expression.index(\"+\")\n",
    "        n = len(expression)\n",
    "        min_value = float(\"inf\")\n",
    "\n",
    "        for i in range(plus_pos):\n",
    "            for j in range(plus_pos+1, n):\n",
    "\n",
    "                a = expression[0: i] if i != 0 else \"1\"\n",
    "                b = expression[i: plus_pos]\n",
    "                c = expression[plus_pos+1: j+1]\n",
    "                d = expression[j+1:] if j != n-1 else \"1\"\n",
    "\n",
    "                value = int(a) * (int(b) + int(c)) * int(d)\n",
    "\n",
    "                if value < min_value:\n",
    "                    min_value = value\n",
    "                    res = expression[:i] + \"(\" + expression[i:j+1] + \")\" + expression[j+1:]\n",
    "                    \n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        a=b=jm=lena=lenb=0\n",
    "        readadd=False\n",
    "        for i in range(len(expression)):\n",
    "            if (ord(expression[i])<ord('0') or ord(expression[i])>ord('9')) and expression[i]!='+': continue\n",
    "            if expression[i]=='+':\n",
    "                readadd=True\n",
    "                continue\n",
    "            if readadd:\n",
    "                b=b*10+int(expression[i])\n",
    "                lenb+=1\n",
    "            else:\n",
    "                a=a*10+int(expression[i])\n",
    "                lena+=1\n",
    "        im=lena\n",
    "        minsum=a+b\n",
    "        for i in range(1,lena+1):\n",
    "            for j in range(lenb):\n",
    "                if i==lena and j==0: continue\n",
    "                if i==lena:\n",
    "                    if (a+b//10**j)*(b%10**j)<minsum:\n",
    "                        im=i\n",
    "                        jm=j\n",
    "                        minsum=(a+b//10**j)*(b%10**j)\n",
    "                elif j==0:\n",
    "                    if (a//10**i)*(a%10**i+b)<minsum:\n",
    "                        im=i\n",
    "                        jm=j\n",
    "                        minsum=(a//10**i)*(a%10**i+b)\n",
    "                else:\n",
    "                    if (a//10**i)*(a%10**i+b//10**j)*(b%10**j)<minsum:\n",
    "                        im=i\n",
    "                        jm=j\n",
    "                        minsum=(a//10**i)*(a%10**i+b//10**j)*(b%10**j)\n",
    "        if im==lena and jm==0: ans='('+expression+')'\n",
    "        elif im==lena: ans='('+str(a)+'+'+str(b//10**jm)+')'+str(b%10**jm)+''\n",
    "        elif jm==0: ans=''+str(a//10**im)+'('+str(a%10**im)+'+'+str(b)+')'\n",
    "        else: ans=''+str(a//10**im)+'('+str(a%10**im)+'+'+str(b//10**jm)+')'+str(b%10**jm)+''\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        # Split the expression into two operands\n",
    "        nums = expression.split('+')\n",
    "        x = nums[0].strip('\"')\n",
    "        y = nums[1].strip('\"')\n",
    "        \n",
    "        forms = {}\n",
    "        \n",
    "        # Iterate over the characters of the first operand\n",
    "        for i in range(len(x)):\n",
    "            x0 = list(x)\n",
    "            x0.insert(i, '(')\n",
    "            \n",
    "            # Iterate over the characters of the second operand\n",
    "            for j in range(len(y)):\n",
    "                y0 = list(y)\n",
    "                y0.insert(j+1, ')')\n",
    "                \n",
    "                # Combine the operands with parentheses and '+'\n",
    "                formula = ''.join(x0 + ['+'] + y0)\n",
    "                \n",
    "                # Calculate the total for different cases of parentheses\n",
    "                if formula[0] == '(' and formula[-1] != ')':\n",
    "                    total = eval(formula.replace(')', ')*'))\n",
    "                elif formula[0] != '(' and formula[-1] == ')':\n",
    "                    total = eval(formula.replace('(', '*('))\n",
    "                elif formula[0] != '(' and formula[-1] != ')':\n",
    "                    formula0 = formula.replace(')', ')*')\n",
    "                    total = eval(formula0.replace('(', '*('))\n",
    "                else:\n",
    "                    total = eval(formula)\n",
    "                \n",
    "                forms[total] = formula\n",
    "        \n",
    "        # Find the formula with the minimum total\n",
    "        min_total = min(forms.keys())\n",
    "        \n",
    "        # Return the formula corresponding to the minimum total\n",
    "        return forms[min_total]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        # Split the expression into two operands\n",
    "        nums = expression.split('+')\n",
    "        x = nums[0].strip('\"')\n",
    "        y = nums[1].strip('\"')\n",
    "        \n",
    "        forms = {}\n",
    "        \n",
    "        # Iterate over the characters of the first operand\n",
    "        for i in range(len(x)):\n",
    "            x0 = list(x)\n",
    "            x0.insert(i, '(')\n",
    "            \n",
    "            # Iterate over the characters of the second operand\n",
    "            for j in range(len(y)):\n",
    "                y0 = list(y)\n",
    "                y0.insert(j+1, ')')\n",
    "                \n",
    "                # Combine the operands with parentheses and '+'\n",
    "                formula = ''.join(x0 + ['+'] + y0)\n",
    "                \n",
    "                # Calculate the total for different cases of parentheses\n",
    "                if formula[0] == '(' and formula[-1] != ')':\n",
    "                    total = eval(formula.replace(')', ')*'))\n",
    "                elif formula[0] != '(' and formula[-1] == ')':\n",
    "                    total = eval(formula.replace('(', '*('))\n",
    "                elif formula[0] != '(' and formula[-1] != ')':\n",
    "                    formula0 = formula.replace(')', ')*')\n",
    "                    total = eval(formula0.replace('(', '*('))\n",
    "                else:\n",
    "                    total = eval(formula)\n",
    "                \n",
    "                forms[total] = formula\n",
    "        \n",
    "        # Find the formula with the minimum total\n",
    "        min_total = min(forms.keys())\n",
    "        \n",
    "        # Return the formula corresponding to the minimum total\n",
    "        return forms[min_total]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        e=expression\n",
    "        a,b = e.split('+')\n",
    "        l1,l2 = len(a),len(b)\n",
    "        p1,p2,min_ = l1-1,1,float('inf')\n",
    "        while p1 >= 0:\n",
    "            while p2 <= l2:\n",
    "                cur = (int(a[p1:]) + int(b[:p2])) * (1 if p1 == 0 else int(a[:p1])) * (1 if p2 == l2 else int(b[p2:]))\n",
    "                if cur < min_: l,r,min_ = p1,p2,cur # 更新l,r\n",
    "                p2 += 1\n",
    "            p1,p2 = p1-1,1\n",
    "        return e[:l] + \"(\" + e[l:l1+r+1] + \")\" + e[l1+r+1:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        a, b = expression.split('+')\n",
    "        ans = int(a) + int(b)\n",
    "        res = '(' + expression + ')'\n",
    "        for i in range(len(a)):\n",
    "            a1 = 1\n",
    "            if i != 0:\n",
    "                a1 = int(a[:i])\n",
    "            a2 = int(a[i:])\n",
    "            for j in range(1, len(b) + 1):\n",
    "                b1 = int(b[:j])\n",
    "                b2 = 1\n",
    "                if j != len(b):\n",
    "                    b2 = int(b[j:])\n",
    "                k = a1 * (a2 + b1) * b2\n",
    "                if k < ans:\n",
    "                    ans = k\n",
    "                    res = a[:i] + '(' + a[i:] + '+' + b[:j] + ')' + b[j:]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        ans_exp, ans_val = '(' + expression + ')', eval(expression)\n",
    "        for i in range(len(left)):\n",
    "            left1, left2 = left[ : i ], left[ i : ]\n",
    "            for j in range(1, len(right) + 1):\n",
    "                right1, right2 = right[ : j ], right[ j : ]\n",
    "                tmp = int(left1 or 1) * (int(left2) + int(right1)) * int(right2 or 1)\n",
    "                if tmp < ans_val:\n",
    "                    ans_exp, ans_val = left1 + '(' + left2 + '+' + right1 + ')' + right2, tmp\n",
    "        return ans_exp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        result = ''\n",
    "        value = 10000000000000\n",
    "        index = 0\n",
    "        i = 0\n",
    "        while i < len(expression):\n",
    "            if expression[i] == '+':\n",
    "                index = i\n",
    "                break\n",
    "            i+=1\n",
    "        i = 0\n",
    "        while i < index:\n",
    "            j = len(expression)-1\n",
    "            while j > index:\n",
    "                before_value = int(expression[0:i]) if i != 0 else 1\n",
    "                last_value = int(expression[j+1:]) if j != len(expression)-1 else 1\n",
    "                tmp_result = (expression[0:i] if i != 0 else '') + '(' + expression[i:index] + '+' + expression[index+1:j+1] + ')' + (expression[j+1:] if j != len(expression)-1 else '')\n",
    "                # print(f'tmp_result = {tmp_result} before_value = {before_value} last_value = {last_value} j = {j}')\n",
    "                exp_value = before_value * (int(expression[i:index]) + int(expression[index+1:j+1])) * last_value\n",
    "                if exp_value < value:\n",
    "                    value = exp_value\n",
    "                    result = tmp_result\n",
    "                j -= 1\n",
    "            i += 1\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        A=expression.split(\"+\")\n",
    "        a=A[0]\n",
    "        b=A[1]\n",
    "        ans=inf\n",
    "        res=''\n",
    "        for i in range(len(a)):\n",
    "            if i==0:\n",
    "                x1=1\n",
    "            else:\n",
    "                x1=int(a[:i])\n",
    "            x2=int(a[i:])\n",
    "            for j in range(len(b)):\n",
    "                y1=int(b[:j+1])\n",
    "                if j+1==len(b):\n",
    "                    y2=1\n",
    "                else:\n",
    "                    y2=int(b[j+1:])\n",
    "                if x1*(x2+y1)*y2<ans:\n",
    "                    ans=x1*(x2+y1)*y2 \n",
    "                    res=a[:i]+\"(\"+a[i:]+\"+\"+b[:j+1]+\")\"+b[j+1:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        left, right = expression.split('+')\n",
    "        l, r = int(left), int(right)\n",
    "        # ans储存第一个括号左边有几个数，加号到第二个括号之间有几个数\n",
    "        ans = (0, len(right))\n",
    "        mn = l + r\n",
    "        \n",
    "        for i in range(len(left)):\n",
    "            l1 = int(left[:i]) if i else 1\n",
    "            l2 = int(left[i:]) if left[i:] else 0\n",
    "            # 加号不能在结尾，例如'(123+)234'\n",
    "            for j in range(1, len(right) + 1):\n",
    "                r1 = int(right[:j])\n",
    "                r2 = int(right[j:]) if right[j:] else 1\n",
    "                total = l1 * (l2 + r1) * r2\n",
    "                if total < mn:\n",
    "                    mn = total\n",
    "                    ans = (i, j)\n",
    "        \n",
    "        i, j = ans\n",
    "        return ''.join((left[:i], '(', left[i:], '+', right[:j], ')', right[j:]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        n = len(expression)\n",
    "        mid = expression.index(\"+\")\n",
    "        best, ans = float(\"inf\"), \"\"\n",
    "        for i in range(mid):\n",
    "            for j in range(mid + 1, n):\n",
    "                result = int(expression[:i] or 1) * (int(expression[i:mid]) + int(expression[mid+1:j+1])) * int(expression[j+1:] or 1)\n",
    "                if result < best:\n",
    "                    best = result\n",
    "                    ans = expression[:i] + \"(\" + expression[i:j+1] + \")\" + expression[j+1:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        plus_p = expression.find('+')\n",
    "        n = len(expression)\n",
    "        temp = float('inf')\n",
    "        ans = ''\n",
    "        for i in range(plus_p):\n",
    "            for j in range(plus_p+2, n+1):\n",
    "                if i == 0:\n",
    "                    pre = 1\n",
    "                else:\n",
    "                    pre = int(expression[:i])\n",
    "                if j == n:\n",
    "                    suf = 1\n",
    "                else:\n",
    "                    suf = int(expression[j:])\n",
    "                if pre * (int(expression[i:plus_p]) + int(expression[plus_p+1:j])) * suf < temp:\n",
    "                    temp = pre * (int(expression[i:plus_p]) + int(expression[plus_p+1:j])) * suf\n",
    "                    ans = expression[:i]+'('+expression[i:j] + ')' +expression[j:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        el = expression.split('+')\n",
    "        n, m = len(el[0]), len(el[1])\n",
    "        ans = '(' + expression + ')', eval('(' + expression + ')')\n",
    "        for i in range(n):\n",
    "            for j in range(1, m + 1):\n",
    "                if i == 0:\n",
    "                    if j == m:\n",
    "                        pass\n",
    "                    else:\n",
    "                        new_exp = '(' + el[0] + '+' + el[1][:j] + ')*' + el[1][j:]\n",
    "                        ans = ans if ans[1] < eval(new_exp) else (new_exp, eval(new_exp))\n",
    "                else:\n",
    "                    if j == m:\n",
    "                        new_exp = el[0][:i] + '*(' + el[0][i:] + '+' + el[1] + ')'\n",
    "                        ans = ans if ans[1] < eval(new_exp) else (new_exp, eval(new_exp))\n",
    "                    else:\n",
    "                        new_exp = el[0][:i] + '*(' + el[0][i:] + '+' + el[1][:j] + ')*' + el[1][j:]\n",
    "                        ans = ans if ans[1] < eval(new_exp) else (new_exp, eval(new_exp))\n",
    "        return ans[0].replace('*', '')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        a,b=expression.split('+')\n",
    "        best=expression\n",
    "        p=int(a)+int(b)\n",
    "        for i in range(len(a)):\n",
    "            for j in range(len(b)):\n",
    "                q=int(a[:i] or 1)*int(b[j+1:] or 1)*(int(a[i:])+int(b[:j+1]))\n",
    "                if q<=p:\n",
    "                    p=q\n",
    "                    best=a[:i]+'('+a[i:]+'+'+b[:j+1]+')'+b[j+1:]\n",
    "        return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        3 <= len(expression) <= 10\n",
    "        a = expression.find(\"+\")\n",
    "        for i in range(len(expression)):\n",
    "            if i!=a:\n",
    "                expression[i] == 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 \n",
    "        b= int(expression[0:a]) + int(expression[a+1:len(expression)])\n",
    "        c=0\n",
    "        d=len(expression)-1\n",
    "        for i in range(a):\n",
    "            for j in range(a+1,len(expression)):\n",
    "                if j == len(expression)-1 and i !=0:\n",
    "                    if b > int(expression[0:i]) * (int(expression[i:a]) + int(expression[a+1:j+1])):\n",
    "                        b = int(expression[0:i]) * (int(expression[i:a]) + int(expression[a+1:j+1]))\n",
    "                        c=i\n",
    "                        d=j\n",
    "                elif i == 0 and j != len(expression)-1:\n",
    "                    if b > (int(expression[i:a]) + int(expression[a+1:j+1])) * int(expression[j+1:len(expression)]):\n",
    "                        b = (int(expression[i:a]) + int(expression[a+1:j+1])) * int(expression[j+1:len(expression)])\n",
    "                        c=i\n",
    "                        d=j\n",
    "                elif i == 0 and j == len(expression)-1:\n",
    "                    if b > int(expression[i:a]) + int(expression[a+1:j+1]):\n",
    "                        b = (int(expression[i:a]) + int(expression[a+1:j+1]))\n",
    "                        c=i\n",
    "                        d=j\n",
    "                else:\n",
    "                    if b > int(expression[0:i]) * (int(expression[i:a]) + int(expression[a+1:j+1])) * int(expression[j+1:len(expression)]):\n",
    "                        b = int(expression[0:i]) * (int(expression[i:a]) + int(expression[a+1:j+1])) * int(expression[j+1:len(expression)])\n",
    "                        c=i\n",
    "                        d=j\n",
    "            \n",
    "        return expression[0:c]+'('+expression[c:d+1]+')'+expression[d+1:len(expression)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeResult(self, expression: str) -> str:\n",
    "        s = expression\n",
    "        n = len(s)\n",
    "        a = s.split('+')\n",
    "        mn, res = inf, \"\"\n",
    "        for i in range(len(a[0])):\n",
    "            l1, l2 = 1 if i == 0 else int(a[0][:i]), int(a[0][i:])\n",
    "            for j in range(1, len(a[1]) + 1):\n",
    "                r1, r2 = int(a[1][:j]), 1 if j == len(a[1]) else int(a[1][j:])\n",
    "                if l1 * r2 * (l2 + r1) < mn:\n",
    "                    mn = l1 * r2 * (l2 + r1)\n",
    "                    res = f'{a[0][:i]}({a[0][i:]}+{a[1][:j]}){a[1][j:]}'\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
